#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> dp(n, vector<int>(m));
        for (int i = 0; i < m; i++) {
            dp[0][i] = matrix[0][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int n = 0;
                if (j - 1 < 0 && j + 1 < m) {
                    n = min(dp[i - 1][j], dp[i - 1][j + 1]);
                }
                else if (j >= 0 && j + 1 >= m) {
                    n = min(dp[i - 1][j - 1], dp[i - 1][j]);
                }
                else if (j - 1 < 0 && j + 1 >= m) {
                    n = dp[i - 1][j];
                }

                else {
                    n = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]);
                }
                dp[i][j] = n + matrix[i][j];
            }
        }
        int len = INT_MAX;
        for (int i = 0; i < m; i++)
        {
            len = min(len, dp[n - 1][i]);
        }
        return len;
    }
};